package 剑指offer;

public class 剑指offer35优化复杂链表的复制不适用Map {

    public static Node1 copyRandomList(Node1 head) {
        if (head == null){
            return null;
        }
        //复制原链表
        Node1 cur = head;
        while (cur != null){
            //如果cur不等于null,设置临时变量保存下一个节点
            Node1 temp = cur.next;
            //创建新节点
            Node1 node = new Node1(cur.val,cur.random,cur.next);
            //将头节点的下一个节点指向新节点
            cur.next = node;
            //将新节点的next指向temp
            node.next = temp;
            //创建完成以后，将cur向后移动两个
            cur = temp;
        }
        //给复制的原链表添加random关系
        cur = head;
        while (cur != null){
            Node1 node = cur.next;
            node.random = cur.random == null ? null : cur.random.next;
            cur = cur.next.next;
        }
        //断开链表
        cur = head;
        Node1 cloneNode = cur.next;
        while (cur != null){
            Node1 node = cur.next;
            cur.next = node.next;
            node.next = node.next == null ? null : node.next.next;
            cur = cur.next;
        }
        return cloneNode;
    }
}
class Node1 {
    int val;
    Node1 next;
    Node random;

    public Node1(int val, Object o, Object o1) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}

